//给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 
//
// 如果数组中不存在目标值 target，返回 [-1, -1]。 
//
// 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4] 
//
// 示例 2： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 6
//输出：[-1,-1] 
//
// 示例 3： 
//
// 
//输入：nums = [], target = 0
//输出：[-1,-1] 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// nums 是一个非递减数组 
// -10⁹ <= target <= 10⁹ 
// 
//
// Related Topics 数组 二分查找 👍 3064 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public static int binarySearchLeftMost(int[] nums, int target){
        int i = 0;
        int j = nums.length - 1;
        int candidate = -1;//记录候选位
        while(i <= j){
            int mid = (i + j ) >>> 1; //右移一边，代表除以2
            if( target < nums[mid]){// 目标在左边
                j = mid -1;
            }else if (nums[mid] < target){// 目标在右边
                i = mid + 1;
            }else{
                candidate = mid;//查找到，先记录侯选位。
                j = mid -1;//继续向左边查找
            }
        }
        return candidate;
    }

    public static int binarySearchRightMost(int[] nums, int target){
        int i = 0;
        int j = nums.length - 1;
        int candidate = -1;
        while(i <= j){
            int mid = (i + j ) >>>1;//右移一位，代表除以2
            if(target < nums[mid]){
                j  = mid - 1;
            }else if(nums[mid] < target){
                i = mid + 1;
            }else {
                candidate = mid;
                i = mid + 1;//继续向右边查找
            }
        }
        return candidate;
    }
    public int[] searchRange(int[] nums, int target) {
        int left = binarySearchLeftMost(nums, target);
        if (left == -1){
            return new int[]{-1, -1};
        }else{
            return new int[] {left, binarySearchRightMost(nums, target)};
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
